<html lang="en">
	<head>
		<title>Yuka | Graph Search</title>
		<meta charset="utf-8">
		<meta name="viewport" content="width=device-width, user-scalable=no, minimum-scale=1.0, maximum-scale=1.0">
		<link rel="stylesheet" type="text/css" href="../../lib/styles.css">
		<link rel="shortcut icon" type="image/x-icon" href="https://mugen87.github.io/yuka/favicon.ico">
	</head>
<body>

	<section id="info">
		<p>
			Click on one of the nodes to perform a graph search.<br/>
			The green line represents the shortest path, the red lines the search tree.
		</p>
	</section>

	<script type="module">

	import * as YUKA from '../../../build/yuka.module.js';
	import * as THREE from 'https://cdn.jsdelivr.net/npm/three@0.109/build/three.module.js';
	import * as DAT from 'https://cdn.jsdelivr.net/npm/dat.gui@0.7.7/build/dat.gui.module.js';

	import { createGraphHelper, createPathHelper, createSearchTreeHelper } from '../common/js/GraphHelper.js';

	let renderer, scene, camera, raycaster;

	let searchTreeHelper, pathHelper, nodes = [];

	let graph;
	let from = 60; // source node index
	let to = 104; // target node index

	const params = {
		algorithm: 'AStar'
	};

	init();

	function init() {

		scene = new THREE.Scene();

		camera = new THREE.PerspectiveCamera( 40, window.innerWidth / window.innerHeight, 0.1, 1000 );
		camera.position.set( 50, 50, 0 );
		camera.lookAt( scene.position );

		raycaster = new THREE.Raycaster();

		// renderer

		renderer = new THREE.WebGLRenderer( { antialias: true } );
		renderer.setPixelRatio( window.devicePixelRatio );
		renderer.setSize( window.innerWidth, window.innerHeight );
		document.body.appendChild( renderer.domElement );

		//

		window.addEventListener( 'resize', onWindowResize, false );
		document.addEventListener( 'mousedown', onDocumentMouseDown, false );

		// graph

		graph = YUKA.GraphUtils.createGridLayout( 50, 10 );

		const graphHelper = createGraphHelper( graph, 0.25 );
		scene.add( graphHelper );

		graphHelper.traverse( ( child ) => {

			if ( child.isMesh ) nodes.push( child );

		} );

		performSearch();

		// dat.gui

		const gui = new DAT.GUI( { width: 300 } );
		gui.add( params, 'algorithm', [ 'AStar', 'Dijkstra', 'BFS', 'DFS' ] ).onChange( performSearch );
		gui.open();

	}

	function performSearch() {

		const graphSearch = new YUKA[ params.algorithm ]( graph, from, to );

		graphSearch.search();

		const searchTree = graphSearch.getSearchTree();
		const path = graphSearch.getPath();

		// update helper

		if ( searchTreeHelper !== undefined && pathHelper !== undefined ) {

			scene.remove( searchTreeHelper );
			scene.remove( pathHelper );

			dispose( searchTreeHelper );
			dispose( pathHelper );

		}

		searchTreeHelper = createSearchTreeHelper( graph, searchTree );
		searchTreeHelper.renderOrder = 1;
		scene.add( searchTreeHelper );

		pathHelper = createPathHelper( graph, path, 0.4 );
		pathHelper.renderOrder = 2;
		scene.add( pathHelper );

		// clean up

		graphSearch.clear();

		//

		renderer.render( scene, camera );

	}

	function dispose( object ) {

		object.traverse( child => {

			if ( child.isMesh || child.isLine ) {

				child.geometry.dispose();
				child.material.dispose();

			}

		} );

	}

	function onDocumentMouseDown( event ) {

		const mouse = new THREE.Vector2();

		mouse.x = ( event.clientX / window.innerWidth ) * 2 - 1;
		mouse.y = - ( event.clientY / window.innerHeight ) * 2 + 1;

		raycaster.setFromCamera( mouse, camera );

		const intersects = raycaster.intersectObjects( nodes );

		if ( intersects.length > 0 ) {

			const intersection = intersects[ 0 ];

			// set new target node

			to = intersection.object.userData.nodeIndex;

			performSearch();

		}

	}

	function onWindowResize() {

		camera.aspect = window.innerWidth / window.innerHeight;
		camera.updateProjectionMatrix();

		renderer.setSize( window.innerWidth, window.innerHeight );
		renderer.render( scene, camera );

	}

	</script>

</body>
</html>
